﻿namespace ConsoleAlgorithms.Tests
{
    public class C07_DynamicProgramming : ITestable
    {
        Dictionary<int, double> kvs = new Dictionary<int, double>();

        public void Test()
        {
            Test3();
        }

        public void Test3()
        {
            int[] p = { 30, 35, 15, 5, 10, 20, 25 };
            var m = MatrixChain(p);
            PrintArray(m, "Matrix M");
        }

        public static void PrintArray(int[,] m, string title = "")
        {
            var len = 6;
            Console.WriteLine($"\n---------------- {title} ---------------");
            Console.Write("A     ");
            for (int i = 0; i < m.GetLength(0); i++)
                Console.Write($"{i + 1,-6}");
            Console.WriteLine();

            for (int i = 0; i < m.GetLength(0); i++)
            {
                Console.Write((i + 1).ToString() + new string(' ', len * i));
                for (int k = i; k < m.GetLength(0); k++)
                    Console.Write($"{m[i, k],6}");
                Console.WriteLine();
            }
            Console.WriteLine($"\n----------------------------------------");
        }

        int[,] MatrixChain(int[] p)
        {
            int[,] m = new int[p.Length - 1, p.Length - 1];
            int[,] s = new int[p.Length - 1, p.Length - 1];

            for (int stepSize = 1; stepSize < p.Length - 1; stepSize++)
            {
                for (int i = 0, j = i + stepSize; i < p.Length - 1 - stepSize; i++, j = i + stepSize)
                {
                    s[i, j] = 0;
                    for (int k = i; k < j; k++)
                    {
                        int t = m[i, k] + m[k + 1, j] + p[i] * p[k + 1] * p[j + 1];
                        if (t < m[i, j] || m[i, j] == 0)
                        {
                            m[i, j] = t;
                            s[i, j] = k;
                        }
                    }
                }
            }

            PrintArray(s, "status");

            return m;
        }


        public void Test2()
        {
            int[] vs = { 30, 35, 15, 5, 10, 20, 25 };
            Dictionary<string, int> kvs = new Dictionary<string, int>();
            var res = trace(1, vs.Length - 1, vs, kvs);
            Console.WriteLine("res: " + res);
        }

        public int trace(int start, int end, int[] vs, Dictionary<string, int> kvs)
        {
            int value = int.MaxValue, k = 0;
            for (int i = start; i < end; i++)
            {
                int v1 = trace(start, i, vs, kvs);
                int v2 = vs[i - 1] * vs[i] * vs[i + 1];
                int v3 = trace(i + 1, end, vs, kvs);
                if (value > v1 + v2 + v3)
                {
                    k = i;
                    value = v1 + v2 + v3;
                }
            }

            if (value == int.MaxValue)
            {
                value = 0;
            }
            else
            {
                Console.WriteLine("k = " + k);
            }

            return value;
        }

        public void Test1()
        {
            int n = 10000;
            DateTime t1 = DateTime.Now;
            double v1 = Factorial(n);
            DateTime t2 = DateTime.Now;

            DateTime t3 = DateTime.Now;
            double v2 = Factorial1(n);
            DateTime t4 = DateTime.Now;

            Console.WriteLine($"v1 = {v1}, v2 = {v2}");
            Console.WriteLine($"t1 = {(t2 - t1).TotalMilliseconds:0.0}ms.");
            Console.WriteLine($"t2 = {(t4 - t3).TotalMilliseconds:0.0}ms.");
        }

        public double Factorial(int n)
        {
            return n > 0 ? n + Factorial(n - 1) : 1;
        }


        public double Factorial1(int n)
        {
            if (kvs.Keys.Contains(n))
                return kvs[n];
            double value = n > 0 ? n + Factorial1(n - 1) : 1;
            kvs[n] = value;
            return value;
        }
    }
}
